/**
 * https://leetcode-cn.com/problems/uOAnQW/
 * 心算挑战
 * 要求选手从 N 张卡牌中选出 cnt 张卡牌，若这 cnt 张卡牌数字总和为偶数, 求最大
 * @param cards 
 * @param cnt 
 */
const maxmiumScore = (cards: number[], cnt: number): number => {
    // 1. 对cards进行排序
    cards.sort((a, b) => b - a)

    let total = 0,
        lastEven = 0,
        lastOdd = 0;

    // 2. 尝试寻找前cnt个数
    for (let i = 0; i < cnt; i++) {
        let item = cards[i]
        total += item;
        if ((item & 1) === 0) lastEven = item;
        else lastOdd = item;
    }

    // 如果total是偶数, 直接返回
    if ((total & 1) === 0) return total;


    const len = cards.length
    let maxOdd = 0,
        maxEven = 0

    for (let i = cnt; i < len; i++) {
        // 存在奇数, 尝试找偶数最大
        if (lastOdd && (cards[i] & 1) === 0 && maxEven === 0) maxEven = total - lastOdd + cards[i]

        // 存在偶数, 尝试找奇数最大
        if (lastEven && (cards[i] & 1) === 1 && maxOdd === 0) maxOdd = total - lastEven + cards[i]
    }

    // 找不到
    return Math.max(maxOdd, maxEven)
};

// 排序 + 回溯
const maxmiumScore2 = (cards: number[], cnt: number): number => {
    // 1. 对cards进行排序
    cards.sort((a, b) => a - b)

    // 存放所有的排列组合结果
    const ret: number[] = [];
    let currTotal = 0,
        ans = 0,
        sign = 0;


    /**
     * 
     * @param count 还剩多少次
     * @param e 到这个索引位置还是有效的
     */
    const dfs = (count: number, e: number) => {
        // 已经找到答案了, 直接返回

        // 终止条件, 开始计数
        if (count === 0) {
            if ((currTotal & 1) === 0 && currTotal > ans) {
                // 更新ans
                ans = currTotal
                ++sign;
            }
            ret.push(currTotal);
            return;
        }

        // 1. 对数组进行处理, 把已经排好的去掉
        console.log(e);
        let arr = cards.slice(0, e);
        // console.log(arr);
        const len = arr.length - 1;
        // 从后往前遍历
        for (let i = len; i >= 0; i--) {
            if (sign < 100) {
                currTotal += arr[i];
                // 对处理下一个元素
                dfs(count - 1, i);

                // 减掉刚才加的
                currTotal -= arr[i]
            }
        }

    }

    // 2. dfs 排列所有可能出现的情况
    dfs(cnt, cards.length)

    // 没有找到, 返回0
    return ans
};

console.log(maxmiumScore([3,3,1], 1))
// console.log(maxmiumScore([1, 2, 8, 9], 3))
// console.log(maxmiumScore([9, 5, 9, 1, 6, 10, 3, 4, 5, 1], 2))